package algorithm.leetcode.I1to100;

import java.util.Arrays;


public class Q34 {

    public int[] searchRange(int[] nums, int target) {
        if (nums[0] > target || nums[nums.length-1] < target) return new int[]{-1, -1};

        int headLow = 0, headHigh = nums.length-1;
        int tailLow = 0, tailHigh = nums.length-1;

        while (headLow < headHigh || tailLow < tailHigh) {

            if (headLow < headHigh) {
                int headMid = ((headHigh-headLow)>>1) + headLow;
                if (nums[headMid] < target) headLow = headMid+1;
                else headHigh = headMid;
            }

            if (tailLow < tailHigh) {
                // 下面这行是本题最难的地方
                int tailMid = ((tailHigh-tailLow+1)>>1) + tailLow;
                if (nums[tailMid] > target) tailHigh = tailMid-1;
                else tailLow = tailMid;
            }
        }

        return tailLow >= headLow ? new int[]{headLow,tailLow} : new int[]{-1, -1};
    }

    public static void main(String[] args) {
        Q34 q34 = new Q34();
        System.out.println(Arrays.toString(q34.searchRange(new int[]{5,2,7,8,8,10}, 8)));
    }

}
